樹是一種抽象資料結構，跟鏈結串列一樣是由節點組成的資料集合。它的形狀類似家族樹，或者說像向下生長的樹，最上面有一個根節點(如下圖A)，每個節點都可以有零個或多的子節點。實作上可以像鏈結串列一樣，由每個節點指向子節點的位址。

圖片來源：維基百科

二分搜尋樹(binary search tree)

我們之前提到，陣列的隨機存取利於實現一些演算法，可是不太容易調整長度；鏈結串列的長度有彈性，但只能線性地存取元素。在一些情況下利用樹的結構，可以兼得兩者的優點：既可以保持資料順序、快速搜尋，又容易插入及刪除節點。

圖片來源：維基百科

二分搜尋樹(或稱二元搜尋樹)，是二元樹的結構，也就是每個節點最多只會有兩個子節點。二分搜尋樹儲存資料的方式如上圖，每個節點的左邊子節點的值會比自己小，右邊子節點的值比自己大。

確保這樣的結構，就可以進行快速的二分搜尋。

從任一個節點來看，其左半邊的所有節點一定都比較小，右半邊的一定都比較大(如同二分搜尋中的有序陣列)，所以從根節點開始搜尋，若目標較小則往左，不用再考慮樹的右半邊，也就是每次的搜尋都可以排除剩下一半的節點，達到O(log n)的搜尋。

值得注意的是，因為樹本身的結構也是將所有節點分為左右兩半，所以樹的高度也會log n。另外，這個結構也體現了二分搜尋中的遞迴概念，也就是樹中任一個節點的左右子結構也各是一個二分搜尋樹，也代表我們可以用程式的遞迴來實作二分搜尋樹。

來源：GeeksforGeeks

def search(root,key):
     
    # 基本情況: 樹不存在或目標在根結點
    if root is None or root.val == key:
        return root
 
    # 目標大於根結點的值
    if root.val < key:
        return search(root.right,key)
   
    # 目標小於根結點的值
    return search(root.left,key)
    
# This code is contributed by Bhavya Jain

如果是要在樹中插入新節點，步驟跟搜尋一樣，要從根節點開始找到新節點的位置，所以執行時間也可以達到O(log n)，而且插入新節點只需改變原本節點的指向，不用更動到其他節點。

潛在問題

二分搜尋樹當然也不是集所有優點於一身，還是有一些實作上必須注意的事情。其中一個問題可能是空間，因為所有的節點都要有更多的空間來儲存參照。

另外一個問題是如果樹的結構不平衡，效能也會變差。想像如果根節點的值最小，後來加入的新節點的值越來越大，這樣整棵樹會只往右邊發展。如此一來，樹的高度就會變得非常高(n)，搜尋或插入的執行時間也會變成O(n)。我們可以透過一些可以自己平衡結構的二分搜尋樹(例如B樹)，來避免這個的問題。